树形目录

作者：陈广
日期：2018-4-15

学了点 JavaScript 和 TypeScript，终于可以开工我的目录树了。对于程序的世界，还有什么比直接做东西更快的学习方法吗？暂时我还没想到。虽然做的过程中可能由于掌握的知识不够而导致各种困难和痛苦，但完成后所带给你的收获，以及对知识点的理解深度，是看书和视频是完全无法比拟的。

需求

首先还是要列出需要完成什么样的功能，然后根据需求决定采用什么数据结构，然后代码实现。

用于客户端展示文章列表
支持无限分级
可折叠
添加新结点？没有的事。那是服务器做的事情
删除结点？没有的事。那是服务器做的事情
修改结点？没有的事。那是服务器做的事情
结点展开收起动画？没有的事，我要的是极速

简而言之，我做的东西很简单。只要服务器给个目录列表，我在浏览器用 JavaScript 展示出来就可以了。当然子结点可展开折叠这是要有的。

数据结构

之前见过两种目录树表示的两种数据结构：

一种在 Vue 的 Element 的 TreeView 里，之前搭茅草房时用过。使用 Json 将子结点嵌套在父结点里面，一层套一层，看得我那个头昏眼花啊！加一个结点那是困难重重，一不小心就踩坑
第二种是放在数组内，每个结点分配一个ID，和PID。PID 为父亲结点的 ID。这种结构简单明了，要说缺点的话，就是大部分操作都需要遍历数组，还要递归。我以前做过类似的东西，相当痛苦。

当然用什么样的数据结构是根据需求来定的，这样用，肯定有这样用的道理。我的需求如此简单，自然就想到用一种更简单、更容易操作的数据结构来实现了。那就来创造一个吧：

使用数组存放，效率当然最高
无 ID，使用结点在数组中的索引来替代
每结点分配一个表示层级的数字：0表示最顶层，1表示第二层，2表示第三层，以此类推
结点按显示时从上下到的顺序存放

就这么简单，来个例子演示一下：

A
B
- C
  - E
  - F
- G
H

以上层次结构就表示为：

条目	层次
A	0
B	0
C	1
D	2
E	2
F	1
G	0

这样表示是有前提的，因为使用数组索引作为其 ID，在插入一个新节点时，其后结点索引都会改变。只是没有增加、删除操作，所以可以这样设计。另外还需注意，一个层次为0的结点如果插入一个层次为2的结点紧随其后，这显然是不对的，这样的错误显然很容易发生，但可以在程序中判断和控制。当然，我们不需要插入功能。

算法

将表示条目的数组转化为 HTML 注入到窗体大概是目录树中最难的算法了，一般是需要使用递归来完成的。但我惊喜地发现，不需要递归也能完成。而且只需一个循环，算法复杂度为O(n)。看来这个数据结构的设计是相当好啊！

实现

实现还是经历了一翻周折，甚至 JavaScript 有些地方让我大跌眼镜。实现得还有些不尽如人意的地方，没办法，无人可问，以后慢慢解决吧。目录树使用 TypeScript 实现，页面直接用 JavaScript。

CgTree.ts

let selectNode: any; //当前选中结点
class CgTree {
    nodes: CgNode[];
    //构造函数
    constructor(div: any, nodes: CgNode[]) {
        selectNode = null;
        this.nodes = nodes;
        div.innerHTML = this.GetHtmlStr(); //注入 HTML
        let liList = div.getElementsByClassName("cgTree_entryLink");
        for (let i = 0; i < liList.length; i++) { //加入事件
            liList[i].addEventListener("click", this.Click);
        }
    }
    //计算结点 HTML
    private GetHtmlStr(): string {
        let str: string = `<ul>`;
        let space: string = "";
        for (let i = 0; i < this.nodes.length; i++) {
            let current = this.nodes[i].level; //当前结点等级
            let next = (i == this.nodes.length - 1) ? 0 : this.nodes[i + 1].level; //下一结点等级
            space = "";
            let temp = current;
            while (temp--) {
                space += "&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp";
            }
            if (current < next) { //有孩子 
                str += `<li><a id="${i}" class="cgTree_entryLink">${space + this.nodes[i].name}</a><ul>`
            }
            else {
                str += `<li><a id="${i}" class="cgTree_entryLink">${space + this.nodes[i].name}</a></li>`
                if (current > next) {
                    let sub = current - next;
                    while (sub--) {
                        str += `</ul></li>`;
                    }
                }
            }
        }
        str += `</ul>`;
        return str;
    }
    //结点单击事件方法
    Click(e): void {
        if (selectNode != undefined) { //选中结点换CSS
            selectNode.setAttribute("class", "cgTree_entryLink");
        }
        this.setAttribute("class", "cgTree_entryLinkSelected");
        selectNode = this;
        //防止事件冒泡
        e.stopPropagation();
    }
}

class CgNode {
    //私有成员变量，用于属性
    private _name: string; //条目名称，用于显示
    private _url: string = "#"; //单击转到的链接地址
    private _level: number; //第几层条目，最顶层为0
    private _isOpen: boolean = false; //是否展开

    //属性
    get name(): string {
        return this._name;
    }

    get url(): string {
        return this._url;
    }

    get level(): number {
        return this._level;
    }

    get isOpen(): boolean {
        return this._isOpen;
    }
    set isOpen(open: boolean) {
        this._isOpen = open;
    }

    constructor(name: string, url: string, lvl: number) {
        this._name = name;
        this._url = url;
        this._level = lvl;
    }
}

由于事件方法包装在类里面，无法直接在 HTML 中关联，只好使用代码加了。我也不知道是否可以在 HTML 中关联类里的方法。另外还声明了一个全局变量selectNode，本应该声明为CgTree的成员变量，但死活记不住状态，搞得我很无语，只能用全局变量了，这破坏了面向对象的原则。JavaScript 的内部机理我是一窍不通啊。

demo.html

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>
    <link rel="stylesheet" href="demo.css">
</head>
<body>
    <div id="Container"></div>
    <p>请输入新条目内容：<input type="text" name="aaa" id="nodeName"></p>
    <button onclick="AddNode(1)">作为子目录加入</button>&nbsp
    <button onclick="AddNode(0)">作为同级目录加入</button>
</body> 
<script src="demo.js"></script>
<script src="CgTree.js"></script>
</html>

没啥好说的，够简单。加入了添加新结点功能，只是为了测试。

demo.js

var cgTree;
var cgNodes
var container
window.onload = function () {
    container = document.getElementById("Container"); //获取id为Container的div
    cgNodes = [
        new CgNode("A", "#", 0),
        new CgNode("B", "#", 0),
        new CgNode("C", "#", 1),
        new CgNode("D", "#", 1),
    ];
    cgTree = new CgTree(container, cgNodes); //创建bitEdit并传入div,在此div内画出按钮   
};

//在当前元素后插入新结点，isChild表示是否作为孩子插入
function AddNode(isChild) {
    if(selectNode==null)
    {
        alert("请先选择一个目录作为插入点！");
        return;
    }
    var index = selectNode.getAttribute("id");
    var selNodeLevel = cgNodes[index].level;
    var level = isChild ? selNodeLevel + 1 : selNodeLevel;
    var newNode = new CgNode(document.getElementById("nodeName").value, "#", level);
    cgNodes.splice(++index, 0, newNode);
    cgTree = new CgTree(container, cgNodes);
}

添加新结点功能只是为了测试画的是否正确。CgTree 本身是没有这个功能的，所以每添加一个结点都会创建新的 CgTree 以重画。

demo.css

body {
	background-color: #ddd;
}

#Container {
	width: 400px;
	border: 4px solid darkgoldenrod;
	border-radius: 3px;
	background-color: coral;
}

#Container ul {
	list-style: none;
	padding: 0;
	margin: 0;
}

#Container li {
	list-style: none;
	margin: 0;
}

.cgTree_entryLink {
	display: block;
	cursor: pointer;
	color: #4e4e4e;
	background: #eeeeee;
	-moz-box-shadow: 0 1px 0 white inset, 0 -1px 0 #d4d4d4 inset;
	-webkit-box-shadow: 0 1px 0 white inset, 0 -1px 0 #d4d4d4 inset;
	box-shadow: 0 1px 0 white inset, 0 -1px 0 #d4d4d4 inset;
	/* text-shadow: 0 -1px 0 rgba(255, 255, 255, 0.3); */
	padding: 4px 4px;
}

.cgTree_entryLinkSelected {
	display: block;
	cursor: pointer;
	color: #6e6e6e;
	background: #CFBB87;
	-moz-box-shadow: 0 1px 0 white inset, 0 -1px 0 #d4d4d4 inset;
	-webkit-box-shadow: 0 1px 0 white inset, 0 -1px 0 #d4d4d4 inset;
	box-shadow: 0 1px 0 white inset, 0 -1px 0 #d4d4d4 inset;
	text-shadow: 0 -1px 0 rgba(255, 255, 255, 0.3);
	padding: 4px 4px;
}

.cgTree_entryLink:hover {
	background: #dfdfdf;
}

这个没啥好讲的，网上拷贝大法。哪个好看拷哪个。

运行

放到窗体上给大家自己玩。